// 判断树B是否为树A的子结构
// 1、树A中找到和树B的根结点值一样的结点R,
// 2、判断以树A中R为更结点的子树是不是包含和树B一样的结构。

#include <iostream>
using namespace std;

struct BinaryTreeNode 
{
    int m_nValue;
    BinaryTreeNode * m_pLeft;
    BinaryTreeNode * m_pRight;
};

bool DoesTree1HaveTree2(BinaryTreeNode * pTree1, BinaryTreeNode * pTree2)
{
    if(pTree2 == NULL)
        return true;
    if(pTree1 == NULL)
        return false;
    if(pTree1->m_nValue != pTree2->m_nValue)
        return false;

    return DoesTree1HaveTree2(pTree1->m_pLeft, pTree2->m_pLeft) && DoesTree1HaveTree2(pTree1->m_pRight, pTree2->m_pRight);
}

bool HasSubTree(BinaryTreeNode * pRoot1, BinaryTreeNode * pRoot2)
{
    bool result = false;

    if(pRoot1 != NULL && pRoot2 != NULL)
    {
        if (pRoot1->m_nValue == pRoot2->m_nValue)
            result = DoesTree1HaveTree2(pRoot1, pRoot2);
        if(!result)
            result = HasSubTree(pRoot1->m_pLeft, pRoot2);
        if(!result)
            result = HasSubTree(pRoot1->m_pRight, pRoot2);
    }
    return result;
}
